package medium前中二叉树;



import org.testng.annotations.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 1)
            return new TreeNode(preorder[0]);
        TreeNode root = new TreeNode(preorder[0]);
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        Map<Integer,Integer> indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        int index= indexMap.get(preorder[0]);
//        for (int i = 0; i < inorder.length; i++) {
//            if (inorder[i]==preorder[0]){
//                index = i;
//                break;
//            }
//        }
        root.left=test(Arrays.copyOfRange(preorder,1,index+1),Arrays.copyOfRange(inorder,0,index));
        root.right=test(Arrays.copyOfRange(preorder,index+1,preorder.length),Arrays.copyOfRange(inorder,index+1,preorder.length));
        return root;
    }
    public TreeNode test(int[] pd, int[] id){
        if (pd.length == 0)
            return null;
        if (pd.length == 1)
            return new TreeNode(pd[0]);
        TreeNode node = new TreeNode(pd[0]);

        int index=-1;
        for (int i = 0; i < id.length; i++) {
            if (id[i]==pd[0]){
                index = i;
                break;
            }
        }
        node.left = test(Arrays.copyOfRange(pd,1,index+1),Arrays.copyOfRange(id,0,index));
        node.right=test(Arrays.copyOfRange(pd,index+1,pd.length),Arrays.copyOfRange(id,index+1,pd.length));
        return node;
    }
    @Test
    public void test(){
        int[] num = {0,1};
        num = Arrays.copyOfRange(num,0,1);
        for (int i:
             num) {
            System.out.println(i);
        }
    }
}
